#!/usr/bin/env python3
# coding: utf-8

from __future__ import print_function, division, unicode_literals


__all__ = ['Node', 'Tree', 'inorder_tree_walk']


class Node:
    def __init__(self, key, left=None, right=None, p=None):
        self.key = key
        self.left = left
        self.right = right
        self.p = p

    def __repr__(self):
        return '<Node{0}>'.format(' {0}'.format(self.key) if self.key else '')


class Tree:
    """
    Binary search tree
    """
    def __init__(self, items=None):
        self.root = None
        if items:
            for x in items:
                self.insert(x)

    def insert(self, node, parent=None):
        """
        @node: a Node object
        @parent: subtree root where we want to insert 'node'
        """
        if self.root is None:
            self.root = node
            return node
        if parent is None:
            parent = self.root
        while parent:
            if node.key <= parent.key:
                if parent.left:
                    parent = parent.left
                else:
                    node.p = parent
                    parent.left = node
                    break  # alt: parent = None
            else:
                if parent.right:
                    parent = parent.right
                else:
                    node.p = parent
                    parent.right = node
                    break  # alt: parent = None
        return node

    def find(self, key):
        node = self.root
        while node and node.key != key:
            if key < node.key:
                node = node.left
            else:
                node = node.right
        return node


def inorder_tree_walk(x):
    if x:
        inorder_tree_walk(x.left)
        print(x.key)
        inorder_tree_walk(x.right)


def tree_insert(t, k):
    z = Node(k)
    x = t.root
    while x:
        z.p = x
        if z.key > x.key:
            x = x.right
        else:
            x = x.left
    if z.p:
        if z.key > z.p.key:
            z.p.right = z
        else:
            z.p.left = z
    else:                   # The tree was empty
        t.root = z
